1. Technical Field of the Invention
The present invention relates generally to a method of reading information optically out of a two-dimensional code made up of a matrix of data cells in a decreased time and a storage medium storing a program used to implement such a method.
2. Background Art
U.S. Pat. No. 5,726,435 filed Mar. 10, 1998, assigned to the same assignee as that of this application teaches a two-dimensional code used in inputting coded information into a computer, for example.
Typical two-dimensional codes have a two-dimensional spread, as shown in FIG. 16(b), which can carry a large amount of information in a narrow area as compared with a bar code, as shown in FIG. 16(a), but the structure thereof is complex.
FIG. 17 shows one example of two-dimensional codes. The two-dimensional code 300 includes three location symbols 310a, 310b, and 310c and arrays of timing cells 320a and 320b. The location symbols 310a to 310c are used in locating the two-dimensional code 300 and each consist geometrically of a plurality of squares different in size. The arrays of timing cells 320a and 320b are each disposed between adjacent two of the location symbols 310a to 310c and consist of a plurality of white and black cells arranged in a reference pattern that are used as indices of data cells arranged in a data field 330.
The two-dimensional code 300 is made up of a square matrix of nxc3x97n cells. Each of the location symbols 310a to 310c consists of a square frame 312 formed with four sides each consisting of 7 cells, a white square frame 314 formed with four sides each consisting of 5 cells, and a black square 316 consisting of 3xc3x973 cells formed on the central portion of the white square frame 314.
When each of the location symbols 310a to 310c is scanned through an optical reader along any line passing through the center thereof, an optical signal pattern which has a brightness component ratio of black:white:black:white:black=1:1:3:1:1 is detected. Thus, when an optical signal pattern having that brightness component ratio is detected during scanning of the two-dimensional code 300, it may be determined as a candidate pattern for any one of the location symbols 310a to 310c. Specifically, when three optical signal patterns each having a brightness component ratio of 1:1:3:1:1 are detected, it may be determined that the two-dimensional code 300 lies on a square area defined by the three optical signal patterns.
The data filed 330 consists of data cells (not shown for the brevity of illustration) each formed with a black or white square indicating logical 0 or 1 of a binary-coded data. Two-dimensional coordinates of each data cell are geometrically calculated in a known algorithm by using the centers of the location symbols 310a to 310c and the timing cells 320a and 320b as indices of the coordinates.
When the two-dimensional code 300 is scanned optically from a slant direction undesirably or when the two-dimensional code 300 printed on a curved surface of an object is scanned optically, it will cause a deformed image of the two-dimensional code 300, as shown in FIG. 18(a), to be captured. Additionally, when the two-dimensional code 300 is printed on the surface of a round bottle, for example, it will cause, as shown in FIG. 18(b), both sides of the two-dimensional code 300 to be deformed greatly. The deformation of the image of the two-dimensional code 300 will result in shift between the actual center and the center of each data cell geometrically calculated in the above manner. If the shift is greater than half a size of each data cell, it produces an error in reading the two-dimensional code 300. The degree of the deformation producing such an error increases as the size of the two-dimensional code 300 is increased for carrying more information.
In order to avoid the above problem, Japanese Patent First Publication No. 10-208001 assigned to the same assignee as that of this application teaches a method of reading information out of a two-dimensional code correctly even if a captured image of the two-dimensional code is deformed. The two-dimensional code has location symbols used in locating a data field and alignment symbols (also called auxiliary symbols) each arranged in a predetermined positional relation to the location symbols. The position of each data cell in the data field in the image of the two-dimensional code is specified by determining the central positions, shapes, and arrangement of the location symbols and the alignment symbols. The central position of each of the alignment symbols is determined by mathematically estimating a central position based on the shape of cells of the location symbols and the central positions of the location symbols and scanning an image of the alignment symbol near the estimated central position to find an actual center of the alignment symbol. One example of such a method of determining the actual center of each alignment symbol is also taught in Japanese Patent First Publication No. 8-185429, however, it has the drawback in that many pixels should be scanned, thus taking a large amount of time to locate each alignment symbol, which will result in an increase in time required for reading information out of the two-dimensional code.
It is therefore a principal object of the present invention to avoid the disadvantages of the prior art.
It is another object of the present invention to provide a method of reading information out of a two-dimensional code in a decreased time.
According to one aspect of the invention, there is provided a method of reading information out of a two-dimensional code made up of a matrix of cells having a given optical pattern. The two-dimensional code has at least one location symbol used to locate the two-dimensional code and at least one alignment symbol used to locate the cells. The method comprises steps of: (a) capturing an image around the two-dimensional code in a bit mapped pattern; (b) detecting a position of the location symbol to determine a position of the two-dimensional code in the captured image; (c) calculating a central position of the alignment symbol in the captured image mathematically using a predetermined positional relation of the alignment symbol to the location symbol; (d) selecting a dot in the captured image lying at the calculated central position of the alignment symbol as a reference brightness check dot and dots lying in some of the cells around one of the cells of the captured image in which the reference brightness check dot exists as surrounding brightness check dots to define an alignment symbol optical pattern with a combination of the reference brightness check dot and the surrounding brightness check dots; (e) comparing the alignment symbol optical pattern with a plurality of reference optical patterns each formed with one of possible combinations of one of the cells lying at an actual central position of the alignment symbol and as many cells arranged adjacent the one of the cells as the surrounding brightness check dots to select one of the reference optical patterns matching up with the alignment symbol optical pattern; (f) correcting the calculated central position of the alignment symbol based on a position of one of the surrounding brightness check dots in the captured image corresponding to the one of the cells of the matched reference optical pattern at the actual central position of the alignment symbol and a geometry of the alignment symbol to determine an actual central position of the alignment symbol in the captured image; (g) determining positions of the cells of the two-dimensional code in the captured image based on at least one of the position of the location symbol and the actual central position of the alignment symbol in the captured image; and (h) reading the cells of the two-dimensional code in the captured image optically to decode the information carried by the two-dimensional code.
In the preferred mode of the invention, the alignment symbol has one of a pattern formed with a central dark cell, an intermediate square frame which surrounds the central dark cell, consists of an array of light pixels, and has a width equivalent to one cell, and an outer square frame which surrounds the intermediate square frame, consists of an array of dark cells, and has a width equivalent to one cell and a pattern formed with a central light cell, an intermediate square frame which surrounds the central dark cell, consists of an array of dark pixels, and has a width equivalent to one cell, and an outer square frame which surrounds the intermediate square frame, consists of an array of light cells, and has a width equivalent to one cell. Each of the reference optical patterns consists of a matrix of 3xc3x973 cells. The number of the reference optical patterns is nine.
Each of the cells of the two-dimensional code is represented in the captured image by a matrix of a plurality of pixels. Each of the reference brightness check dot and the surrounding brightness check dots is represented by one pixel. The alignment symbol optical pattern is formed with a combination of brightness levels of pixels representing the reference brightness check dot and the surrounding brightness check dots. The brightness level of each of the pixels is determined by considering brightness levels of pixels surrounding thereof into account.
Each of the pixels representing the captured image of the two-dimensional code is one of light and dark pixels. The brightness level of each of the pixels representing the reference brightness check dot and the surrounding brightness check dots is determined based on which of the number of light pixels and the number of dark pixels is greater in an area surrounding the each of the pixels.
The method further comprises the step of determining whether light and dark pixels are mixed in a given area around the reference brightness check dot or not. If it is determined that the light and dark pixels are mixed in the given area, the reference brightness check dot is shifted by a given distance in a given direction determined based on a geometry and a brightness pattern of the alignment symbol to a place of the captured image of the two-dimensional code where there is no mix of light and dark pixels, after which the brightness level of each of the pixels representing the reference brightness check dot and the surrounding brightness check dots is determined.
The given direction in which the reference brightness check dot is shifted may be a direction where the number of either of light pixels and dark pixels in the given area around the shifted reference brightness check dot is expected to increase.
The given direction in which the reference brightness check dot is shifted may alternatively be a direction toward one of a collection of light pixels and a collection of dark pixels in the given area around the reference brightness check dot which forms a portion of the intermediate square frame of the two-dimensional code.
The given distance by which the reference brightness check dot is shifted may be equivalent to a given number of pixels that is identical with a given fraction of one cell.
The given distance by which the reference brightness check dot is shifted is equivalent to a given number of pixels that is identical with half a cell.
The given distance by which the reference brightness check dot is shifted may alternatively be equivalent to a given number of pixels regardless of a size of the cells.
According to another aspect of the invention, there is provided a method of reading information out of a two-dimensional code which is made up of a matrix of cells having a given optical pattern and which has location symbols used to locate the two-dimensional code and alignment symbols used to locate the cells. A first one of the alignment symbols is provided at a position on the two-dimensional code which is specified in a given positional relation to the location symbols. The method comprises the steps of: (a) capturing an image around the two-dimensional code in a bit mapped pattern; (b) detecting positions of the location symbols to determine a position of the two-dimensional code in the captured image; (c) calculating a central position of the first alignment symbol in the captured image mathematically using the given positional relation to the location symbols; (d) calculating a central position of a second one of the alignment symbols in the captured image mathematically using a positional relation to the first alignment symbol and the location symbols; (e) selecting a dot in the captured image lying at the calculated central position of each of the alignment symbols as a reference brightness check dot and dots lying in some of the cells of the captured image located around one of the cells in which the reference brightness check dot exists as surrounding brightness check dots to define an alignment symbol optical pattern with a combination of the reference brightness check dot and the surrounding brightness check dots; (f) comparing the alignment symbol optical pattern of each of the alignment symbols with a plurality of reference optical patterns each formed with one of possible combinations of one of the cells lying at an actual central position of each of the alignment symbols and as many cells arranged adjacent the one of the cells as the surrounding brightness check dots to select one of the reference optical patterns matching up with a corresponding one of the alignment symbol optical patterns; (g) determining a central position of each of the alignment symbols in the captured image based on a position of one of the surrounding brightness check dots corresponding to the one of the cells of the matched reference optical pattern at the actual central position of a corresponding one of the alignment symbols and a geometry of the corresponding one of the alignment symbols; (h) determining a position of each of the cells of the two-dimensional code in the captured image based on the position of one of the location symbols or the actual central position of one of the alignment symbols located near a corresponding one of the cells in the captured image; and (i) reading the cells of the two-dimensional code in the captured image optically to decode the information carried by the two-dimensional code.
In the preferred mode of the invention, the method further comprises the step of calculating a central position of a third one of the alignment symbols in the captured image mathematically using a positional relation to the first and second alignment symbols.
The two-dimensional code also has a format code which is located in a given positional relation to one of the location symbols and which carries information about an arrangement of the alignment symbols in the two-dimensional code. The method further comprises the steps of, after the position of the two-dimensional code is determined, detecting the format code based on the positions of the detected location symbols and reading the information out of the format code about the arrangement of the alignment symbols. The central positions of the alignment symbols are calculated based on the information read out of the format code.
The format code also carries information about the number of the cells in the two-dimensional code. The method further comprises the steps of, after the position of the two-dimensional code is determined, detecting the format code based on the positions of the detected location symbols and reading the information out of the format code about the number of the cells in the two-dimensional code. The positions of the cells are determined based on the read information on the number of the cells.
According to the third aspect of the invention, there is provided a storage medium storing a computer-implemented program for reading information out of a two-dimensional code in any one of methods as described above.